package com.example.sort;

import java.util.Arrays;

/**
 * @author: Bin.L
 * @date: 2022/7/21  10:39
 * @description: 排序复习 - 冒泡排序
 */
public class BubbleSort {

    /**
     * 冒泡排序是一种稳定排序
     * : 想邻的元素两两比较, 当一个元素大于右侧相邻元素则交换位置(单向位置交换), 小于则位置不变; 总归遍历(元素数量-1)次
     */
    public static void main(String[] args) {
        oneVersion();
        twoVersion();
        threeVersion();
    }

    /**
     * 冒泡排序
     */
    public static void oneVersion() {
        int[] ints = {4, 5, 1, 9, 12, 6, 19, 33, 2};
        for (int i = 0; i < ints.length - 1; i++) {
            System.out.println("循环 " + i + " 次 " + Arrays.toString(ints));
            for (int j = 0; j < ints.length - i - 1; j++) {
                int tmp = 0;
                if (ints[j] > ints[j + 1]) {
                    tmp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 优化 (判断出数列有序 - 判断前面数据是否有序来减少遍历次数)
     */
    public static void twoVersion() {
        int[] ints = {1, 2, 3, 9, 4, 12, 7, 8, 11};
        for (int i = 0; i < ints.length - 1; i++) {
            System.out.println("循环 " + i + " 次 " + Arrays.toString(ints));
            // 有序标记, 默认初始值为true
            boolean isSorted = true;
            for (int j = 0; j < ints.length - i - 1; j++) {
                int tmp = 0;
                if (ints[j] > ints[j + 1]) {
                    tmp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = tmp;
                    isSorted = false;
                }
            }
            // isSorted 为 true 元素有序, 无需再交换, 直接跳出大循环
            if (isSorted) {
                break;
            }
        }
        System.out.println(Arrays.toString(ints));
    }


    /**
     * 优化 (判断出数列有序 - 判断前面数据是否有序来减少遍历次数, 及后续数据有序 - 判断后面数据是否有序减少遍历次数 )
     */
    public static void threeVersion() {
        int[] ints = {5, 2, 1, 7, 9, 13, 15};
        for (int i = 0; i < ints.length - 1; i++) {
            System.out.println("循环 " + i + " 次 " + Arrays.toString(ints));
            // 有序标记, 默认初始值为true
            boolean isSorted = true;
            //无序数列边界, 每次比较只需到这里为止
            int sortBorder = ints.length - 1;
            for (int j = 0; j < sortBorder; j++) {
                // 边界 - 可能减少嵌套循环比较数
                int tmp = 0;
                if (ints[j] > ints[j + 1]) {
                    tmp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = tmp;
                    isSorted = false;
                    sortBorder = j;
                }
            }
            // isSorted 为 true 元素有序, 无需再交换, 直接跳出大循环
            if (isSorted) {
                break;
            }
        }
        System.out.println(Arrays.toString(ints));
    }
}
